package com.wuyou.dataStructure.tree;

import cn.hutool.core.collection.EnumerationIter;

import java.util.HashMap;
import java.util.Map;

/**
 * 662. 二叉树最大宽度
 *
 * @Date 2024/11/11 14:49
 * @Author 无忧
 */
public class WidthOfBinaryTree {


    /**
     * 二叉树每层的元素数：2^(n-1)
     * 即每层最大宽度为：2^(n-1)
     *
     * @param root
     * @return
     */
    public int sol_1(TreeNode root) {
        if (root == null) {
            return 0;
        }

        dfs(root, 1, 1);
        return maxWidth;
    }

    int maxWidth = 0;
    Map<Integer, Integer> lMap = new HashMap<>();
    Map<Integer, Integer> rMap = new HashMap<>();

    /**
     * Breadth First Search 宽度优先搜索(BFS)
     * Depth First Search 深度优先搜索(DFS)
     * 1
     * 2(1*2) 3(1*2+1)
     * 4(2*2) 5(2*2+1) 6(3*2) 6(3*2+1)
     *
     * @param root
     * @return
     */
    public void dfs(TreeNode root, int idx, int depth) {
        if(root == null) return;
        if (root.left != null && !lMap.containsKey(depth)) {
            lMap.put(depth, idx * 2);
        }
        if (root.right != null) {
            rMap.put(depth, idx * 2 + 1);
        }

        maxWidth = Math.max(maxWidth, rMap.get(depth) - lMap.get(depth));
        dfs(root.left, idx << 1, depth + 1);
        dfs(root.right, idx << 1 | 1, depth + 1);
    }
}
